import numpy as np


def solvePackage(n: int, w: np.array, v: np.array, W: int):
    """
    :param n: 数量
    :param w: 单个物体质量
    :param v: 单个物体价值
    :param W: 总质量
    :return:
    """

    C = np.zeros((n + 1, W + 1))

    for i in range(n):
        C[i][0] = 0
    for i in range(W):
        C[0][i] = 0

    for i in range(1, n + 1):
        for j in range(1, W + 1):
            if j < w[i - 1]:
                C[i][j] = C[i - 1][j]
            else:
                C[i][j] = max(C[i - 1][j], C[i - 1][j - w[i - 1]] + v[i - 1])
    return C


def getSolution(n, w, W, C):
    """
    :param n: 数量
    :param w: 单个物体质量
    :param W: 总质量
    :param C: 生成的动态规划矩阵
    :return:
    """
    j = W
    x = np.zeros(n)
    for i in range(n, 0, -1):
        if C[i][j] == C[i - 1][j]:
            x[i - 1] = 0
        else:
            x[i - 1] = 1
            j -= w[i - 1]
    return x


if __name__ == "__main__":
    n = 11
    w = np.array([2, 6, 3, 4, 2, 8, 2, 4, 7, 5, 1])
    v = np.array([10, 23, 5, 34, 23, 17, 22, 32, 12, 15, 32])
    W = 15

    C = solvePackage(n, w, v, W)
    x = getSolution(n, w, W, C)

    for item in C:
        print(item)

    # print("Output:\n", C)
    print("packages:", x)
